#include "DynamicArray.h"
#include <iostream>
#include <cmath>


DynamicArray::DynamicArray() : capacity(10), size(0)
{
    this->a = new ElementType[capacity];
}

DynamicArray::DynamicArray(const DynamicArray &array)
{
    capacity = array.capacity;
    size = array.size;
    a = new ElementType[capacity];
    for (int i = 0; i < size; i++)
    {
        a[i] = array.a[i];
    }
}

void DynamicArray::operator=(const DynamicArray &array)
{
    delete[] this->a;
    capacity = array.capacity;
    size = array.size;
    a = new ElementType[capacity];
    for (int i = 0; i < size; i++)
    {
        a[i] = array.a[i];
    }
}

DynamicArray::~DynamicArray()
{
    delete[] a;
}

// 尾插法
void DynamicArray::InsertTail(const ElementType &element)
{
    if (size >= capacity)
    {
        capacity *= 2;
        ElementType *newP = new ElementType[capacity];
        for (int i = 0; i < size; i++)
        {
            newP[i] = a[i];
        }
        delete[] a;
        a = newP;
    }
    a[size++] = element;
}
// 头插法
void DynamicArray::InsertHead(const ElementType &element)
{
    if (size >= capacity)
    {
        capacity *= 2;
        ElementType *newP = new ElementType[capacity];
        for (int i = 0; i < size; i++)
        {
            newP[i] = a[i];
        }
        delete[] a;
        a = newP;
    }
    for (int i = size; i > 0; i--)
        a[i] = a[i - 1];
    a[0] = element;
    size++;
}
// 中间插入
void DynamicArray::InsertByIndex(const ElementType &element, int index)
{
    if (index < 0 || index > size)
    {
        std::cout << "非法插入位置!\n";
        return;
    }
    if (size >= capacity)
    {
        capacity *= 2;
        ElementType *newP = new ElementType[capacity];
        for (int i = 0; i < size; i++)
        {
            newP[i] = a[i];
        }
        delete[] a;
        a = newP;
    }
    for (int i = size; i > index; i--)
        a[i] = a[i - 1];
    a[index] = element;
    size++;
}

bool DynamicArray::operator==(const DynamicArray &array)
{
    if (size != array.size)
        return false;
    int index = 0;
    while (index < size)
    {
        if (a[index++] != array.a[index++])
            return false;
    }
    return true;
}

// 有序
bool DynamicArray::IsChild(const DynamicArray &array)
{
    int count = 0;
    for (int i = 0; i < size; i++)
    {
        if (a[i] == array.a[count])
        {
            count++;
        }
    }
    return count == array.size;
}

//滑动窗口算法  O(n^2)
bool DynamicArray::IsConChild(const DynamicArray &array)
{
    for(int i = 0;i<=size-array.size;i++)
    {
        if(Subsquence(i,array.size) == array)
        {
            return true;
        }
    }
    return false;
}

DynamicArray DynamicArray::Subsquence(int index, int len)
{
    DynamicArray sub;
    for(int i = index; i < index + len;i++)
    {
        sub.InsertTail(a[i]);
    }
    return sub;
}

void DynamicArray::Sort()
{
    FastSort(0, size - 1, 0, 2 * log2(size));
}
void DynamicArray::Duplicate()
{
    for (int i = 1; i < size; i++) // O(n)
    {
        if (a[i] == a[i - 1])
        {
            RemoveByIndex(i);
            i--;
        }
    }
}

// 归并排序：双指针  O(n)
DynamicArray DynamicArray::Merge(const DynamicArray &a)
{
    int first = 0;
    int second = 0;
    DynamicArray result;
    // 两个数列都没到末尾
    while (first < this->size && second < a.size)
    {
        if (this->a[first] < a.a[second])
            result.InsertTail(this->a[first++]);
        else
            result.InsertTail(a.a[second++]);
    }
    while (first < this->size)
        result.InsertTail(this->a[first++]);
    while (second < a.size)
        result.InsertTail(a.a[second++]);
    return result;
}

// 找交集
// 两个数列有序
DynamicArray DynamicArray::FindInterSection(const DynamicArray &array)
{
    int first = 0;
    int second = 0;
    DynamicArray result;
    while (first < size && second < array.size)
    {
        if (a[first] == array.a[second])
        {
            result.InsertTail(a[first]);
            second++;
        }
        else if (a[first] < array.a[second])
        {
            first++;
        }
        else
        {
            second++;
        }
    }
    return result;
}

DynamicArray DynamicArray::FindUnionSet(const DynamicArray &array)
{
    int first = 0;
    int second = 0;
    DynamicArray result;
    while (first < size && second < array.size)
    {
        if (a[first] == array.a[second])
        {
            result.InsertTail(a[first]);
            second++;
            first++;
        }
        else if (a[first] < array.a[second])
        {
            result.InsertTail(a[first++]);
        }
        else
        {
            result.InsertTail(array.a[second++]);
        }
    }
    while (first < this->size)
        result.InsertTail(this->a[first++]);
    while (second < array.size)
        result.InsertTail(array.a[second++]);
    // result.Duplicate();
    return result;
}

DynamicArray DynamicArray::FindDifference(const DynamicArray &array)
{
    int first = 0;
    int second = 0;
    DynamicArray result;
    while (first < size && second < array.size)
    {
        if (a[first] == array.a[second])
        {
            second++;
            first++;
        }
        else if (a[first] < array.a[second])
        {
            result.InsertTail(a[first++]);
        }
        else
        {
            result.InsertTail(array.a[second++]);
        }
    }
    while (first < this->size)
        result.InsertTail(this->a[first++]);
    while (second < array.size)
        result.InsertTail(array.a[second++]);
    return result;
}

void DynamicArray::FastSort(int start, int end, int depth, int MaxDepth)
{
    if (start >= end) // 终止条件
        return;
    // 递归的深度已经超过最大深度
    if (depth > MaxDepth)
    {
        // 改用插入排序
        std::cout << "插入排序" << std::endl;
        InsertSort(start, end);
    }
    // 如果没有超过最大深度
    // 用快速排序
    else
    {
        // 分组
        int pos = Partition(start, end);
        // 递归
        FastSort(start, pos - 1, depth + 1, MaxDepth);
        FastSort(pos + 1, end, depth + 1, MaxDepth);
    }
}

void DynamicArray::InsertSort(int start, int end)
{
    for (int i = start + 1; i <= end; i++)
    {
        int j = i;       // 当前要插入的数的下标
        int temp = a[i]; // 要插入的值
        for (; j > start; j--)
        {
            if (a[j - 1] > temp) // 前面这个数比我大
                a[j] = a[j - 1];
            else // 前面这个数比我小
                break;
        }
        a[j] = temp;
    }
}

int DynamicArray::Partition(int start, int end)
{
    int left = start;
    int right = end;
    int temp = a[left]; // 将最左边的值定为基准值
    while (left < right)
    {
        // 右边往左动，找比基准值小的数
        while (a[right] > temp && left < right)
            right--;
        if (left < right)
            a[left++] = a[right]; // 把右边比基准值小的数扔到左边

        // 左边往右动，找比基准值大的数
        while (a[left] < temp && left < right)
            left++;
        if (left < right)
            a[right--] = a[left]; // 把左边比基准值大的数扔到右边
    }
    a[left] = temp;
    return left;
}

// 快速排序 : 双指针 + 递归
void DynamicArray::FastSort(int start, int end)
{
    if (start >= end) // 终止条件
        return;
    int left = start;
    int right = end;
    int temp = a[left]; // 将最左边的值定为基准值
    while (left < right)
    {
        // 右边往左动，找比基准值小的数
        while (a[right] > temp && left < right)
            right--;
        if (left < right)
            a[left++] = a[right]; // 把右边比基准值小的数扔到左边

        // 左边往右动，找比基准值大的数
        while (a[left] < temp && left < right)
            left++;
        if (left < right)
            a[right--] = a[left]; // 把左边比基准值大的数扔到右边
    }
    a[left] = temp;
    FastSort(start, left - 1);
    FastSort(right + 1, end);
}

void DynamicArray::show()
{
    for (int i = 0; i < size; i++)
    {
        std::cout << a[i] << " ";
    }
    std::cout << std::endl;
}

void DynamicArray::SetFreePtr(void (*FreePtr)(ElementType))
{
    for(int i = 0;i<size;i++)
    {
        this->FreePtr = FreePtr;
    }
}



DynamicArray::ElementType *DynamicArray::FindByIndex(int index)
{
    if (index < 0 || index >= size)
    {
        std::cout << "插入位置非法!\n";
        return nullptr;
    }
    return &a[index];
}

DynamicArray DynamicArray::FindByElement(const ElementType &element)
{
    DynamicArray result;
    for (int i = 0; i < size; i++)
    {
        if (a[i] == element)
            result.InsertTail(i);
    }
    return result;
}

void DynamicArray::RemoveByIndex(ElementType index)
{
    if (index < 0 || index >= size)
    {
        std::cout << "插入位置非法!\n";
        return;
    }
    for (int i = index; i < size - 1; i++)
    {
        a[i] = a[i + 1];
    }
    size--;
}

void DynamicArray::RemoveByElement(ElementType element)
{
    for (int i = 0; i < size; i++)
    {
        if (a[i] == element)
        {
            RemoveByIndex(i);
            i--;
        }
    }
}

void DynamicArray::UpdateByIndex(int index, const ElementType &element)
{
    if (index < 0 || index >= size)
    {
        std::cout << "插入位置非法!\n";
        return;
    }
    a[index] = element;
}

void DynamicArray::UpdateByElement(const ElementType &oldValue, const ElementType &newValue)
{
    for (int i = 0; i < size; i++)
    {
        if (a[i] == oldValue)
        {
            a[i] = newValue;
        }
    }
}

int DynamicArray::BinarySearch(int element)
{
    int left = 0;
    int right = size - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (a[mid] > element)
            right = mid - 1;
        else if (a[mid] < element)
            left = mid + 1;
        else
            return mid;
    }
    return -1;
}

